
package ai;

import java.awt.Point;

public class GameSolover
{
	public static final int	N				= 6;	//栅格边长
	public static final int	K				= 5;
	int [][]				waterState		= null;
	int [][]				iniWaterState	= null;
	int [][]				mostValueState	= null;
	int [][]				mostValueAction	= null;
	int []					mostValueCombo	= null;
	int						mostValue2		= 0;
	int						mostValue1		= 0;	//最多可付出的水滴代价
	int						mostValue		= -10;	//最多可付出的水滴代价
	
	public GameSolover(int [][] state)
	{
		this.waterState = GameSolover.getDeepCopy(state);
		this.iniWaterState = GameSolover.getDeepCopy(state);
	}
	
	private void resetState()
	{
		this.waterState = GameSolover.getDeepCopy(this.iniWaterState);
	}
	
	private int drop(int x, int y, int op, int curCombo)
	{
		if((x < 0) || (y < 0) || (x > (GameSolover.N - 1)) || (y > (GameSolover.N - 1)))
		{
			return curCombo;
		}
		if(op == 0) //点击该栅格加入水滴
		{
			curCombo = 0;
			if(this.waterState[x][y] < GameSolover.K)
			{
				this.waterState[x][y]++;
			}
		}else
		//表示加入的水滴为破裂的水滴释放的水滴
		{
			if(this.waterState[x][y] == 0) //该水滴按照原来的方向继续移动
			{
				if(op == 1)
				{
					curCombo = this.drop(x - 1, y, 1, curCombo); //go on moving to left
				}else if(op == 2)
				{
					curCombo = this.drop(x + 1, y, 2, curCombo); //go on moving to right
				}else if(op == 3)
				{
					curCombo = this.drop(x, y - 1, 3, curCombo); //go on moving to up
				}else if(op == 4)
				{
					curCombo = this.drop(x, y + 1, 4, curCombo); //go on moving to down
				}
			}else if(this.waterState[x][y] < GameSolover.K)
			{
				this.waterState[x][y]++;
			}
		}
		//若水滴满,则破裂,并释放水滴
		if(this.waterState[x][y] == GameSolover.K)
		{
			this.waterState[x][y] = 0; //水滴破裂
			curCombo += 1;
			curCombo = this.drop(x - 1, y, 1, curCombo); //release a drop moving to left
			curCombo = this.drop(x + 1, y, 2, curCombo); //release a drop moving to right
			curCombo = this.drop(x, y - 1, 3, curCombo); //release a drop moving to up
			curCombo = this.drop(x, y + 1, 4, curCombo); //release a drop moving to down
		}
		return curCombo;
	}
	
	public void solove()
	{
		int max = (this.checkWater() / 3) + 1;
		if(max < 4)
		{
			max = 4;
		}else if(max > 6)
		{
			max = 6;
		}
		System.out.println("设定搜索深度为：" + max + "\n-------------------------");
		for(int i = 1; i <= max; i++)//最多搜索6层,否则时间不够
		{
			System.out.println("当前搜索序列深度" + i + "  ");
			long startTime = System.currentTimeMillis();
			if(i < 5)
			{
				this.allCase1(new int[i][2], 0);
			}else
			{
				this.allCase2(new int[i][2], 0);
			}
			long endTime = System.currentTimeMillis();
			System.out.println("用时：" + ((float) (endTime - startTime) / 1000) + "s");
		}
		System.out.println("搜索完成\n-------------------------");
	}
	
	private void allCase1(int [][] action, int length)
	{
		if(length == action.length)
		{
			this.calc(action);
			return;
		}
		for(int i = 0; i < GameSolover.N; i++)
		{
			for(int j = 0; j < GameSolover.N; j++)
			{
				action[length][0] = i;
				action[length][1] = j;
				if((this.waterState[i][j] == 0))
				{
					this.allCase2(action, length + 1);
				}else
				{
					this.allCase1(action, length + 1);
				}
			}
		}
	}
	
	private void allCase2(int [][] action, int length)
	{
		if(length == action.length)
		{
			this.calc(action);
			return;
		}
		for(int i = 0; i < GameSolover.N; i++)
		{
			for(int j = 0; j < GameSolover.N; j++)
			{
				action[length][0] = i;
				action[length][1] = j;
				if((this.waterState[i][j] != 0))
				{
					this.allCase2(action, length + 1);
				}
			}
		}
	}
	
	private void calc(int [][] action)
	{
		int curValue2 = 0;
		int curValue1 = 0;
		int curValue = 0;
		this.resetState();
		int [] comboNum = new int[action.length];
		for(int i = 0; i < action.length; i++)
		{
			int combo = this.drop(action[i][0], action[i][1], 0, 0); //点击该栅格
			comboNum[i] = combo;
			curValue2 += combo;
			curValue1 += combo / 3;
		}
		curValue = curValue1 - action.length;
		if(curValue2 != 0)
		{
			if((curValue > this.mostValue))
			{
				this.mostValue2 = curValue2;
				this.mostValue1 = curValue1;
				this.mostValue = curValue;
				this.mostValueState = GameSolover.getDeepCopy(this.waterState);
				this.mostValueAction = GameSolover.getDeepCopy(action);
				this.mostValueCombo = GameSolover.getDeepCopy(comboNum);
				System.out.println("收益提升为：" + this.mostValue);
			}else if((curValue == this.mostValue) && (curValue <= 0))
			{
				if((curValue1 > this.mostValue1))
				{
					this.mostValue2 = curValue2;
					this.mostValue1 = curValue1;
					this.mostValueState = GameSolover.getDeepCopy(this.waterState);
					this.mostValueAction = GameSolover.getDeepCopy(action);
					this.mostValueCombo = GameSolover.getDeepCopy(comboNum);
					System.out.println("收益提升为：" + this.mostValue);
				}else if((curValue1 == this.mostValue1))
				{
					if(curValue2 < this.mostValue2)
					{
						this.mostValue2 = curValue2;
						this.mostValueState = GameSolover.getDeepCopy(this.waterState);
						this.mostValueAction = GameSolover.getDeepCopy(action);
						this.mostValueCombo = GameSolover.getDeepCopy(comboNum);
						System.out.println("收益提升为：" + this.mostValue);
					}
				}
			}
		}
	}
	
	public static int [] getDeepCopy(int [] ary)
	{
		int [] result = new int[ary.length];
		for(int j = 0; j < ary.length; j++)
		{
			result[j] = ary[j];
		}
		return result;
	}
	
	public static int [][] getDeepCopy(int [][] ary)
	{
		int [][] result = new int[ary.length][ary[0].length];
		for(int i = 0; i < result.length; i++)
		{
			for(int j = 0; j < result[i].length; j++)
			{
				result[i][j] = ary[i][j];
			}
		}
		return result;
	}
	
	public static Point [] getDeepPointCopy(Point [] action)
	{
		Point [] result = new Point[action.length];
		for(int i = 0; i < action.length; i++)
		{
			result[i] = new Point(action[i].x, action[i].y);
		}
		return result;
	}
	
	public int checkWater()
	{
		int num = 0;
		for(int i = 0; i < this.waterState.length; i++)
		{
			for(int j = 0; j < this.waterState[i].length; j++)
			{
				if(this.waterState[i][j] != 0)
				{
					num++;
				}
			}
		}
		return num;
	}
	
	/**
	 * @return mostValueState
	 */
	public int [][] getMostValueState()
	{
		return this.mostValueState;
	}
	
	/**
	 * @return mostValueAction
	 */
	public int [][] getMostValueAction()
	{
		return this.mostValueAction;
	}
	
	/**
	 * @return mostValueCombo
	 */
	public int [] getMostValueCombo()
	{
		return this.mostValueCombo;
	}
	
	/**
	 * @return mostValue
	 */
	public int getMostValue()
	{
		return this.mostValue;
	}
}
